package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class Permutations{
    public static void main(String[] args) {
         
         Solution solution = new Permutations().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private ArrayList<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<Integer> path = new ArrayList<>();
        backTrack(nums,0,path);
        return result;
    }

        private void backTrack(int[] nums, int k, ArrayList<Integer> path) {
            if (k == nums.length){
                result.add(new ArrayList<>(path));
                return;
            }

            for (int i = 0; i < nums.length; i++) {
                if (path.contains(nums[i])){
                    continue;
                }
                path.add(nums[i] );
                backTrack(nums,k+1,path);
                path.remove(path.size()-1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}